package mo.tags.divideandconquer;

import mo.common.TreeNode;

public class L105 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        int len = preorder.length;
        return buildTree(preorder, 0, len-1, inorder, 0, len-1);
    }

    private TreeNode buildTree(int[] preorder, int pFrom, int pTo, int[] inorder, int iFrom, int iTo) {
        if (pTo < pFrom) {
            return null;
        }
        TreeNode cur = new TreeNode(preorder[pFrom]);
        int middle = 0;
        for (int i = iFrom; i <= iTo; i++) {
            if (inorder[i] == preorder[pFrom]) {
                middle = i;
                break;
            }
        }
        int leftLen = middle - iFrom;
        cur.left = buildTree(preorder, pFrom+1, pFrom+leftLen, inorder, iFrom, middle-1);
        cur.right = buildTree(preorder, pFrom+leftLen+1, pTo,inorder, middle+1, iTo);
        return cur;
    }

}
